package done.easy_201_300;

import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

/**
 * 268. Missing Number 缺失数字
 * <p>
 * 给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
 * <p>
 * 示例 1:
 * 输入: [3,0,1]
 * 输出: 2
 * 示例 2:
 * 输入: [9,6,4,2,3,5,7,0,1]
 * 输出: 8
 * <p>
 * 思路：
 * 既然0到n之间少了一个数，我们将这个少了一个数的数组合0到n之间完整的数组异或一下，
 * <p>
 * num1 = 0^1^2^3^4^5^6^7^9
 * num2 = 0^1^2^3^4^5^6^7^8^9
 * num1^num2 == 8
 * <p>
 * 将整个数组所有元素一一进行异或 是顺序无关的
 * 那么相同的数字都变为0了，剩下的就是少了的那个数字了。
 *
 * @author wangxiaozhe
 */
@Slf4j
public class MissingNumber {

    @SuppressWarnings("all")
    public int missingNumber(int[] nums) {
        // 190329 first
        return -1;
    }

    @Test
    public void test() {
        int[] nums = new int[]{9, 6, 4, 2, 3, 7, 0, 8, 1};
        log.info("result:{}", missingNumber(nums));
    }
}












































/*
public int missingNumber(int[] nums) {
    int sum = nums.length;
    for (int i = 0; i < nums.length; i++) {
        sum ^= nums[i];
        sum ^= i;
    }
    return sum;
}
*/
